package com.study;

import java.util.LinkedList;
import java.util.Queue;

/**
 * @program: leetcode
 * @author: jzhou
 * @date: 2022-11-15 14:37
 * @version: 1.0
 * @description: 省份数量
 * 省份是一组直接或简介相连的城市，组内不含其他不相连城市，给一个 n * n 的矩阵，判断省份个数 isConnected[i][j] = 1 表示相连
 * 类似问题还有 朋友圈 和 亲戚问题
 **/
public class GroupMerge {
    public static void main(String[] args) {
        System.out.println(getProvinceBfs(new int[][]{{1,1,0},{1,1,0},{0,0,1}}));
        System.out.println(getProvinceBfs(new int[][]{{1,0,0},{0,1,0},{0,0,1}}));
        System.out.println(getProvinceBfs(new int[][]{{1,1,0},{1,1,1},{0,1,1}}));
        System.out.println(getProvinceBfs(new int[][]{{1,1,0,0},{1,1,1,1},{0,1,1,0},{0,1,0,1}}));
    }

    /**
     * 深度优先遍历解法
     * 需要一个 visited 数组 记录那些城市被标记过了
     * @param citys
     * @return
     */
    private static int getProvinceDfs(int[][] citys) {
        boolean[] visited = new boolean[citys.length];
        int province = 0;
        for (int i = 0; i < citys.length; i++) {
            if (!visited[i]){
                province++;
                dfs(i,citys.length,visited,citys);
            }
        }
        return province;
    }

    private static void dfs(int i, int length, boolean[] visited, int[][] citys) {
        for (int j = i; j < length; j++) {
            if (citys[i][j] == 1 && !visited[j]){
                visited[j] = true;
                dfs(j,length,visited,citys);
            }
        }
    }


    /**
     * 广度优先遍历解法 ， 需要借助一个queue
     * 需要一个 visited 数组 记录那些城市被标记过了
     * @param citys
     * @return
     */
    private static int getProvinceBfs(int[][] citys) {
        boolean[] visited = new boolean[citys.length];
        int province = 0;
        Queue<Integer> queue = new LinkedList<>();
        for (int i = 0; i < citys.length; i++) {
            if (!visited[i]) {
                queue.offer(i);
                while (!queue.isEmpty()){
                    Integer k = queue.poll();
                    for (int j = 0; j < citys.length; j++) {
                        if (citys[k][j] == 1 && !visited[j]) {
                            visited[j] = true;
                            queue.offer(j);
                        }
                    }
                }
                province++;
            }

        }

        return province;
    }
}
